package com.fanshuai.algorithms.datastructure.linear;

import com.fanshuai.queue.Queue;
import com.fanshuai.stack.LinkedStack;
import com.fanshuai.stack.Stack;

/**
 * 栈实现队列
 * 实现方式：使用2个栈s1和s2，s1 弹出元素, 22 加入元素
 *
 * 入队：s2元素入栈
 * 出队：如果s1非空，s1出栈；否则将s2元素push到s1，然后s1出栈
 * 获取栈顶元素：
 */
public class StackedQueue<E> implements Queue<E> {
    private Stack<E> stack1;
    private Stack<E> stack2;

    public StackedQueue() {
        stack1 = new LinkedStack<>();
        stack2 = new LinkedStack<>();
    }

    @Override
    public int size() {
        return stack1.size() + stack2.size();
    }

    @Override
    public boolean isEmpty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }

    @Override
    public boolean isFull() {
        return false;
    }

    /**
     * 入队：stack2 push元素即可
     * @param data
     */
    @Override
    public void enqueue(E data) {
        stack2.push(data);
    }

    /**
     * 出队：如果stack1空，则将stack2的元素加入stack1，然后弹出stack1栈顶元素
     * @return
     */
    @Override
    public E dequeue() {
        if (isEmpty()) {
            return null;
        }
        if (stack1.isEmpty()) {
            while (!stack2.isEmpty()) {
                E data = stack2.pop();
                stack1.push(data);
            }
        }

        return stack1.pop();
    }

    /**
     *
     * @return
     */
    @Override
    public E peek() {
        if (stack1.isEmpty()) {
            while (!stack2.isEmpty()) {
                E data = stack2.pop();
                stack1.push(data);
            }
        }

        return stack1.peek();
    }

    public static void main(String[] args) {
        Queue<Integer> queue = new StackedQueue<>();

        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        System.out.println("size=" + queue.size());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());

        queue.enqueue(2);
        queue.enqueue(3);
        queue.enqueue(4);

        System.out.println("size=" + queue.size());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
    }
}
